9.8.4 Nesting and Fixed Points

The H V R [nest] command applies a function to a given argument repeatedly. It takes two values, ‘a’ and ‘n’, from the stack, where ‘n’ must be an integer. It then applies the function nested ‘n’ times; if the function is ‘f’ and ‘n’ is 3, the result is ‘f(f(f(a)))’. The number ‘n’ may be negative if Calc knows an inverse for the function ‘f’; for example, ‘nest(sin, a, -2)’ returns ‘arcsin(arcsin(a))’.

The H V U [anest] command is an accumulating version of nest: It returns a vector of ‘n+1’ values, e.g., ‘[a, f(a), f(f(a)), f(f(f(a)))]’. If ‘n’ is negative and ‘F’ is the inverse of ‘f’, then the result is of the form ‘[a, F(a), F(F(a)), F(F(F(a)))]’.

The H I V R [fixp] command is like H V R, except that it takes only an ‘a’ value from the stack; the function is applied until it reaches a “fixed point,” i.e., until the result no longer changes.

The H I V U [afixp] command is an accumulating fixp. The first element of the return vector will be the initial value ‘a’; the last element will be the final result that would have been returned by fixp.

For example, 0.739085 is a fixed point of the cosine function (in radians): ‘cos(0.739085) = 0.739085’. You can find this value by putting, say, 1.0 on the stack and typing H I V U C. (We use the accumulating version so we can see the intermediate results: ‘[1, 0.540302, 0.857553, 0.65329, ...]’. With a precision of six, this command will take 36 steps to converge to 0.739085.)

Newton’s method for finding roots is a classic example of iteration to a fixed point. To find the square root of five starting with an initial guess, Newton’s method would look for a fixed point of the function ‘(x + 5/x) / 2’. Putting a guess of 1 on the stack and typing H I V R ' ($ + 5/$)/2 RET quickly yields the result 2.23607. This is equivalent to using the a R (calc-find-root) command to find a root of the equation ‘x^2 = 5’.

These examples used numbers for ‘a’ values. Calc keeps applying the function until two successive results are equal to within the current precision. For complex numbers, both the real parts and the imaginary parts must be equal to within the current precision. If ‘a’ is a formula (say, a variable name), then the function is applied until two successive results are exactly the same formula. It is up to you to ensure that the function will eventually converge; if it doesn’t, you may have to press C-g to stop the Calculator.

The algebraic fixp function takes two optional arguments, ‘n’ and ‘tol’. The first is the maximum number of steps to be allowed, and must be either an integer or the symbol ‘inf’ (infinity, the default). The second is a convergence tolerance. If a tolerance is specified, all results during the calculation must be numbers, not formulas, and the iteration stops when the magnitude of the difference between two successive results is less than or equal to the tolerance. (This implies that a tolerance of zero iterates until the results are exactly equal.)

Putting it all together, ‘fixp(<(# + A/#)/2>, B, 20, 1e-10)’ computes the square root of ‘A’ given the initial guess ‘B’, stopping when the result is correct within the specified tolerance, or when 20 steps have been taken, whichever is sooner.